#define _CRT_SECURE_NO_WARNINGS 1

//1. 删除链表中等于给定值 val 的所有节点。
//203. 移除链表元素
//难度简单
//给你一个链表的头节点 head 和一个整数 val ，
//请你删除链表中所有满足 Node.val == val 的节点，
//并返回 新的头节点 。
//示例 1：
//输入：head = [1, 2, 6, 3, 4, 5, 6], val = 6
//输出：[1, 2, 3, 4, 5]
//示例 2：
//输入：head = [], val = 1
//输出：[]
//示例 3：
//输入：head = [7, 7, 7, 7], val = 7
//输出：[]
//
//提示：
//? 列表中的节点数目在范围[0, 10 ^ 4] 内
//? 1 <= Node.val <= 50
//? 0 <= val <= 50

 //* Definition for singly-linked list.
// struct ListNode 
//{
//      int val;
//      struct ListNode *next;
//};
// 
// //示例 1：
////输入：head = [1, 2, 6, 3, 4, 5, 6], val = 6
////输出：[1, 2, 3, 4, 5]
////示例 2：
////输入：head = [], val = 1
////输出：[]
////示例 3：
////输入：head = [7, 7, 7, 7], val = 7
////输出：[]
//#include<stdio.h>
//#include<malloc.h>
//#include<stdlib.h>
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    struct ListNode* cur = head;
//    struct ListNode* prev = NULL;
//    while (cur)
//    {
//        if (cur->val == val)
//        {
//            if (cur == head)
//            {
//                head = cur->next;
//                free(cur);
//                cur = head;
//            }
//            else
//            {
//                prev->next = cur->next;
//                free(cur);
//                cur = prev->next;
//            }
//        }
//        else
//        {
//            prev = cur;
//            cur = cur->next;
//        }
//    }
//    return head;
//}
//
//int main()
//{
//    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    n1->val = 7;
//    n2->val = 7;
//    n3->val = 7;
//    n4->val = 7;
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = n4;
//    n4->next = NULL;
//    
//    struct ListNode* head = removeElements(n1, 7);
//
//    return 0;
//}

//2. 反转一个单链表
//206. 反转链表
//难度简单
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//示例 1：
//输入：head = [1, 2, 3, 4, 5]
//输出：[5, 4, 3, 2, 1]
//示例 2：
//输入：head = [1, 2]
//输出：[2, 1]
//示例 3：
//输入：head = []
//输出：[]
//
//提示：
//? 链表中节点的数目范围是[0, 5000]
//? - 5000 <= Node.val <= 5000
//
//进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

  //Definition for singly-linked list.
//#include<stdio.h>
//#include<malloc.h>
//#include<stdlib.h>
//  struct ListNode {
//      int val;
//      struct ListNode *next;
//  };
//struct ListNode* reverseList(struct ListNode* head) {
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* cur = head;
//    struct ListNode* newHead = cur;
//    while (cur->next)
//    {
//        cur = cur->next;
//    }
//    while(cur!=head)
//    {
//        struct ListNode* prev = head;
//        while (prev->next != cur)
//        {
//            prev = prev->next;
//        }
//        cur->next = prev;
//        cur = prev;
//    }
//}

////时间O(N)的代码（三指针）：
//struct ListNode* reverseList(struct ListNode* head) {
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* n1 = NULL, * n2 = head, * n3 = head->next;
//    while (n2)
//    {
//        n2->next = n1;//翻转
//        n1 = n2;//迭代往后走
//        n2 = n3;
//        if (n3 != NULL)
//        {
//            n3 = n3->next;
//        }
//    }
//    return n1;
//}
////时间O(N)的代码（头插）：
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* newHead = NULL, * cur = head;
//    while (cur)
//    {
//        struct ListNode* curNext = cur->next;
//        cur->next = newHead;//头插
//        newHead = cur;//迭代往后走
//        cur = curNext;
//    }
//    return newHead;
//}

//3.返回链表的中间结点
//876. 链表的中间结点
//难度简单
//给定一个头结点为 head 的非空单链表，返回链表的中间结点。
//如果有两个中间结点，则返回第二个中间结点。
//示例 1：
//输入：[1, 2, 3, 4, 5]
//输出：此列表中的结点 3 (序列化形式：[3, 4, 5])
//返回的结点值为 3 。(测评系统对该结点序列化表述是[3, 4, 5])。
//注意，我们返回了一个 ListNode 类型的对象 ans，这样：
//ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
//示例 2：
//输入：[1, 2, 3, 4, 5, 6]
//输出：此列表中的结点 4 (序列化形式：[4, 5, 6])
//由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
//提示：
//? 给定链表的结点数介于 1 和 100 之间。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* cur = head;
//    int count = 0;
//    while (cur != NULL)
//    {
//        cur = cur->next;
//        count++;//计算链表长度
//    }
//    struct ListNode* middle = head;
//    for (int i = 0;i < count / 2;i++)//如5的话3次，6的话4次
//    {
//        middle = middle->next;
//    }
//    return middle;
//}
//快慢指针：
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast != NULL && fast->next != NULL)
//    {
//        fast = fast->next->next;//快指针一次走两步
//        slow = slow->next;//慢指针一次走一步
//    }
//    return slow;
//}

//4. 输出该链表中倒数第k个结点
//剑指 Offer 22. 链表中倒数第k个节点
//输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，
//本题从1开始计数，即链表的尾节点是倒数第1个节点。
//例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。
//这个链表的倒数第 3 个节点是值为 4 的节点。
//示例：
//给定一个链表 : 1->2->3->4->5, 和 k = 2.
//返回链表 4->5.
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//    struct ListNode* getKthFromEnd(struct ListNode* head, int k) {
//
//}
//（这题没给范围，有点不严谨，但是懂思路就好了）
//力扣这题是后更新的，所以测试用例更不严谨
//普通思路的代码：
//这题和上一题的普通思路一样，相当于遍历两次链表
//struct ListNode* getKthFromEnd(struct ListNode* head, int k) {
//    struct ListNode* cur = head;
//    int count = 0;
//    while (cur != NULL)
//    {
//        cur = cur->next;
//        count++;//计算链表长度
//    }
//    struct ListNode* newHead = head;
//    for (int i = 0;i < count - k;i++)
//    {
//        newHead = newHead->next;
//    }
//    return newHead;
//}
//运用快慢指针的代码：
//struct ListNode* getKthFromEnd(struct ListNode* head, int k) {
//    struct ListNode* fast = head, * slow = head;
//    while (k--)
//    {
//        if (fast == NULL)
//        {
//            return NULL;
//        }
//        fast = fast->next;//快指针先走k步
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;//快慢指针一起走
//    }
//    return slow;
//}

//5. 合并两个有序链表为一个新的有序链表
//21. 合并两个有序链表
//难度简单
//将两个升序链表合并为一个新的 升序 链表并返回。
//新链表是通过拼接给定的两个链表的所有节点组成的。
//示例 1：
//输入：l1 = [1, 2, 4], l2 = [1, 3, 4]
//输出：[1, 1, 2, 3, 4, 4]
//示例 2：
//输入：l1 = [], l2 = []
//输出：[]
//示例 3：
//输入：l1 = [], l2 = [0]
//输出：[0]
//提示：
//? 两个链表的节点数目范围是[0, 50]
//? - 100 <= Node.val <= 100
//? l1 和 l2 均按 非递减顺序 排列

 //Definition for singly-linked list.
//#include<stdio.h>
// struct ListNode {
//     int val;
//     struct ListNode *next;
// };
// struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//     if (list1 == NULL)
//     {
//         return list2;
//     }
//     if (list2 == NULL)
//     {
//         return list1;
//     }
//     struct ListNode* cur = list1->val <= list2->val ? list1 : list2;
//     struct ListNode* new = cur;
//     while (list1 && list2)
//     {
//         if (list1->val <= list2->val)
//         {
//             cur->next = list1;
//             cur = list1;
//             list1 = list1->next;
//         }
//         else
//         {
//             cur->next = list2;
//             cur = list2;
//             list2 = list2->next;
//         }
//     }
//     if (list1 == NULL)
//     {
//         cur->next = list2;
//     }
//     else
//     {
//         cur->next = list1;
//     }
//     return new;
// }

//6. 分割链表成两部分
//面试题 02.04.分割链表
//难度中等
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
//使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要 保留 每个分区中各节点的初始相对位置。
//示例 1：
//输入：head = [1, 4, 3, 2, 5, 2], x = 3
//输出：[1, 2, 2, 4, 3, 5]
//示例 2：
//输入：head = [2, 1], x = 2
//输出：[1, 2]
//提示：
//? 链表中节点的数目在范围[0, 200] 内
//? - 100 <= Node.val <= 100
//? - 200 <= x <= 200
//struct ListNode* partition(struct ListNode* pHead, int x) {
//    //开哨兵位头节点 方便尾插
//    struct ListNode* small_head = (struct ListNode*)malloc(sizeof(struct ListNode));
//    small_head->next = NULL;
//    struct ListNode* large_head = (struct ListNode*)malloc(sizeof(struct ListNode));
//    large_head->next = NULL;
//    struct ListNode* small_tail = small_head;
//    struct ListNode* large_tail = large_head;
//    while (pHead)
//    {
//        if (pHead->val < x)
//        {
//            small_tail->next = pHead;
//            small_tail = small_tail->next;
//        }
//        else
//        {
//            large_tail->next = pHead;
//            large_tail = large_tail->next;
//        }
//        pHead = pHead->next;
//    }
//    large_tail->next = NULL;//易忘记 可能成环
//    small_tail->next = large_head->next;
//    struct ListNode* new_head = small_head->next;
//    free(small_head);//临时指针可以不置空
//    free(large_head);
//    return new_head;
//}
//
// 
//7. 链表的回文结构
//234. 回文链表
//剑指 Offer II 027. 回文链表
//（这两题是一模一样的）
//难度简单
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；
//否则，返回 false 。
// 
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* newHead = NULL, * cur = head;
//    while (cur)
//    {
//        struct ListNode* curNext = cur->next;
//        cur->next = newHead;//头插
//        newHead = cur;//迭代往后走
//        cur = curNext;
//    }
//    return newHead;
//}
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast != NULL && fast->next != NULL)
//    {
//        fast = fast->next->next;//快指针一次走两步
//        slow = slow->next;//慢指针一次走一步
//    }
//    return slow;
//}
//bool isPalindrome(struct ListNode* head) {
//    struct ListNode* mid = middleNode(head);
//    struct ListNode* reverse_mid = reverseList(mid);
//    while (head && reverse_mid)
//    {
//        if (head->val != reverse_mid->val)
//        {
//            return false;
//        }
//        else
//        {
//            head = head->next;
//            reverse_mid = reverse_mid->next;
//        }
//    }
//    return true;
//}
//8. 找两个链表的第一个公共结点
//160. 相交链表
//面试题 02.07.链表相交
//剑指 Offer 52. 两个链表的第一个公共节点
//（链接题目都是一样的，给这么多链接只是为了知道这题在很多地方出现）
//难度简单
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。
//图示两个链表在节点 c1 开始相交：
//题目数据 保证 整个链式结构中不存在环。
//注意，函数返回结果后，链表必须 保持其原始结构 。
//提示：
//? listA 中节点数目为 m
//? listB 中节点数目为 n
//? 1 <= m, n <= 3 * 104
//? 1 <= Node.val <= 105
//? 0 <= skipA <= m
//? 0 <= skipB <= n
//? 如果 listA 和 listB 没有交点，intersectVal 为 0
//? 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
//进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* tailA = headA;
//    struct ListNode* tailB = headB;
//    int lenA = 1, lenB = 1;
//    while (tailA->next)
//    {
//        tailA = tailA->next;
//        lenA++;
//    }
//    while (tailB->next)
//    {
//        tailB = tailB->next;
//        lenB++;
//    }
//    if (tailA != tailB)
//    {
//        return NULL;
//    }
//    int gap = abs(lenA - lenB);
//    //gap 差值 abs求整数绝对值函数 头文件：stdlib.h
//    while (gap--)
//    {
//        if (lenA > lenB)
//        {
//            headA = headA->next;
//        }
//        else if (lenB > lenA)
//        {
//            headB = headB->next;
//        }
//    }
//    while (headA != headB)//注意不能比较next又返回next（可能为空）血的教训
//    {
//        headA = headA->next;
//        headB = headB->next;
//    }
//    return headA;
//}

//9. 判断链表中是否有环
//141. 环形链表
//难度简单
//给你一个链表的头节点 head ，判断链表中是否有环。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
//为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置
//（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
//如果链表中存在环 ，则返回 true 。 否则，返回 false 。
//暴力求解代码：
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* head1 = head, * head2 = head;
//    int x = 10000, y = 10000;
//    while (x-- && head1 && head2)
//    {
//        while (y-- && head2)
//        {
//            if (head2->next == head1)
//            {
//                return true;
//            }
//            head2 = head2->next;
//        }
//        head1 = head1->next;
//        if (head2)
//        {
//            head2 = head;
//        }
//    }
//    return false;
//}
//快慢指针代码：
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        if (fast->next == slow)
//        {
//            return true;
//        }
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return false;
//}

//10. 返回链表入环的第一个节点
//142. 环形链表 II
//难度中等
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
//不允许修改 链表。
//公式 + 快慢指针代码：
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//        {
//            struct ListNode* meet = slow;
//            while (meet != head)
//            {
//                meet = meet->next;//一个指针从相遇点走
//                head = head->next;//一个指针从头走
//            }
//            return meet;//会在入环的第一个节点相遇
//        }
//    }
//    return NULL;
//}

//11. 返回链表的深度拷贝
//138. 复制带随机指针的链表
//难度中等
//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，
//该指针可以指向链表中的任何节点或空节点。
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，
//其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向
//复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
//复制链表中的指针都不应指向原链表中的节点 。
//struct Node* copyRandomList(struct Node* head) {
//    //1.插入复制节点到原节点的后面
//    struct Node* cur = head;
//    while (cur)
//    {
//        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//        copy->val = cur->val;
//        copy->next = cur->next;//插入copy节点
//        cur->next = copy;
//
//        cur = copy->next;
//    }
//    //2.根据原节点处理复制节点的random
//    cur = head;
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        if (cur->random == NULL)
//        {
//            copy->random = NULL;
//        }
//        else
//        {
//            copy->random = cur->random->next;
//        }
//        cur = copy->next;
//    }
//    //3.复制节点解下来链接成一个新链表，恢复原链表链接关系
//    struct Node* copy_head = NULL, * copy_tail = NULL;
//    cur = head;
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//        if (copy_head == NULL)//第一次进来
//        {
//            copy_head = copy_tail = copy;
//        }
//        else
//        {
//            copy_tail->next = copy;
//            copy_tail = copy;
//        }
//        cur->next = next;
//        cur = next;
//    }
//    return copy_head;
//}

//147. 对链表进行插入排序
//给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
//插入排序 算法的步骤 :
//插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
//每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
//重复直到所有输入数据插入完为止。
//下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
//对链表进行插入排序。
//示例 1：
//输入: head = [4, 2, 1, 3]
//输出 : [1, 2, 3, 4]
//示例 2：
//输入: head = [-1, 5, 3, 4, 0]
//输出 : [-1, 0, 3, 4, 5]
//
//提示：
//
//列表中的节点数在[1, 5000]范围内
//- 5000 <= Node.val <= 5000
//struct ListNode* insertionSortList(struct ListNode* head) {
//    struct ListNode* new_head = malloc(sizeof(struct ListNode));
//    new_head->val = 0;
//    new_head->next = head;//新开一个节点指向头，最后返回这个节点的next
//    struct ListNode* end = head;//设置end是已经插入好的链表的最后一个
//    struct ListNode* cur = head->next;
//    while (cur)
//    {
//        if (end->val <= cur->val) //找比 已经插入好的最后一个 小的
//        {
//            end = end->next;
//        }
//        else
//        {
//            struct ListNode* prev = new_head;
//            while (prev->next->val <= cur->val) //找到了就再找cur应该插入的位置
//            {
//                prev = prev->next;
//            }
//            //插入
//            end->next = cur->next;
//            cur->next = prev->next;
//            prev->next = cur;
//        }
//        cur = end->next;//cur=已经插入好的链表的最后一个的下一个，重复循环
//    }
//    return new_head->next;
//}

//答案二：
///*
//解题思路：
//此题可以先创建一个排序空链表，对于每一个节点找到它在排序链表中的合适位置，然后进入插入操作
//*/
//

//13. 删除链表中重复的结点
//删除链表中重复的结点_牛客题霸_牛客网(nowcoder.com)
//JZ76 删除链表中重复的结点
//中等 通过率：22.17 % 时间限制：1秒 空间限制：64M
//在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
//数据范围：链表长度满足 0≤n≤1000 ，链表中的值满足 1≤val≤1000
//进阶：空间复杂度 O(n) ，时间复杂度 O(n)
//例如输入 {
//	1, 2, 3, 3, 4, 4, 5
//}时，对应的输出为{ 1,2,5 }，对应的输入输出链表如下图所示：
//示例1
//输入：
//	{ 1,2,3,3,4,4,5 }
//		返回值：
//	{ 1,2,5 }
//		示例2
//		输入：
//	{ 1,1,1,8 }
//		返回值：
//	{ 8 }
//struct ListNode* deleteDuplication(struct ListNode* pHead) {
//    if (pHead == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* new_head = malloc(sizeof(struct ListNode));
//    new_head->val = 0;
//    new_head->next = pHead;//新开一个节点指向头，最后返回这个节点的next
//    struct ListNode* cur = new_head;
//    while (cur->next && cur->next->next)
//    {
//        if (cur->next->val == cur->next->next->val)
//        {
//            int tmp = cur->next->val;//遇到两个节点相同的，记录下来并跳过
//            while (cur->next && tmp == cur->next->val)
//            {
//                cur->next = cur->next->next;
//            }
//        }
//        else
//        {
//            cur = cur->next;
//        }
//    }
//    return new_head->next;
//}